package com.test18_链表;

/**
 * 链表的实现类
 */
public class LinkImpl<T> implements ILink<T> {
    /** 定义描述节点的结构类 */
    private class Node<T> {
        private T data;     // 保存所有数据
        private Node next;  // 描述下一个节点

        public Node(T data) {
            this.data = data;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        /** 进行节点的追加 */
        public void addNode(Node newNode) {
            if (this.next == null) {
                this.next = newNode;
            } else {
                this.next.addNode(newNode);
            }
        }
    }
    // ================= 链表实现的相关处理操作 =================
    private Node root;  // 根节点
    private Node lastNode;  // 保存最后一个节点
    private int count;  // 统计计数

    /** 实现数据增加 */
    @Override
    public void add(T data) {
        if (data == null) {
            return;
        }
        Node<T> newNode = new Node<>(data);     // 创建新的数据节点
        if (this.root == null) {
            this.root = newNode;    // 保存根节点
            this.lastNode = newNode;    // 保存最后一个节点
        } else {
            // this.root.addNode(newNode);
            this.lastNode.next = newNode;   // 保存新节点
            this.lastNode = newNode;    // 改变节点
        }
        this.count++;
    }

    /** 获取元素个数 */
    @Override
    public int size() {
        return this.count;
    }

    /** 判断是否为空链表 */
    @Override
    public boolean isEmpty() {
        return this.count == 0;
    }

    /** 将链表数据转换为数组 */
    @Override
    public Object[] toArray() {
        if (this.count == 0) {
            return null;
        }
        Object[] result = new Object[this.count];
        int foot = 0;   // 操作角标
        Node node = this.root;
        while (node != null) {
            result[foot++] = node.data;
            node = node.next;   // 获取下一个节点
        }
        return result;
    }

    /** 根据索引获取数据 */
    @Override
    public T get(int index) {
        if (index < 0 || index >= this.count) {     // 当前索引无效
            return null;
        }
        int foot = 0;   // 操作角标
        Node node = this.root;
        while (node != null) {
            if (index == foot) {
                return (T) node.data;
            }
            node = node.next;
            foot++;
        }
        return null;
    }

    /** 根据索引修改数据，并返回原始数据 */
    @Override
    public T set(int index, T data) {
        if (index < 0 || index >= this.count) {     // 当前索引无效
            return null;
        }
        T result = null;    // 要返回的数据
        int foot = 0;   // 操作角标
        Node node = this.root;
        while (node != null) {
            if (index == foot) {
                result = (T) node.data;
                node.data = data;
            }
            node = node.next;
            foot++;
        }
        return result;  // 返回原始数据内容
    }

    /** 判断数据是否存在 */
    @Override
    public boolean contains(T data) {
        if (this.root == null || data == null) {
            return false;
        }
        Node node = this.root;
        while (node != null) {
            if (node.data.equals(data)) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    /** 删除数据，并返回删除的数据内容 */
    @Override
    public T remove(T data) {
        if (!this.contains(data)) {     // 数据不存在
            return null;
        }
        T result = null;
        if (this.root.data.equals(data)) {  // 是否是根节点
            result = (T) this.root.data;
            this.root = this.root.next;
        } else {
            Node parentNode = this.root;
            Node node = this.root.next;
            while (node != null) {
                if (node.data.equals(data)) {
                    result = (T) node.data;
                    parentNode.next = node.next;
                    this.count--;   // 计数减1
                }
                parentNode = node;
                node = node.next;
            }
        }
        return result;  // 返回删除的数据内容
    }

    /** 清空链表 */
    @Override
    public void clear() {
        this.root = null;   // 断开链表所有节点
        this.count = 0;     // 保存元素个数为0
    }
}
